{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #132 Pattern"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #array #binary-search #ordered-set #monotonic-stack"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #数组 #二分查找 #有序集合 #单调栈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: find132pattern"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #132 模式"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>nums</code> ，数组中共有 <code>n</code> 个整数。<strong>132 模式的子序列</strong> 由三个整数 <code>nums[i]</code>、<code>nums[j]</code> 和 <code>nums[k]</code> 组成，并同时满足：<code>i < j < k</code> 和 <code>nums[i] < nums[k] < nums[j]</code> 。</p>\n",
    "\n",
    "<p>如果 <code>nums</code> 中存在 <strong>132 模式的子序列</strong> ，返回 <code>true</code> ；否则，返回 <code>false</code> 。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,3,4]\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>序列中不存在 132 模式的子序列。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [3,1,4,2]\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>序列中有 1 个 132 模式的子序列： [1, 4, 2] 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [-1,3,2,0]\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>序列中有 3 个 132 模式的的子序列：[-1, 3, 2]、[-1, 3, 0] 和 [-1, 2, 0] 。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == nums.length</code></li>\n",
    "\t<li><code>1 <= n <= 2 * 10<sup>5</sup></code></li>\n",
    "\t<li><code>-10<sup>9</sup> <= nums[i] <= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [132-pattern](https://leetcode.cn/problems/132-pattern/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [132-pattern](https://leetcode.cn/problems/132-pattern/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4]', '[3,1,4,2]', '[-1,3,2,0]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find132pattern(self, nums: List[int]) -> bool:\n",
    "        n=len(nums)\n",
    "        leftMin=[float(\"inf\")]*n\n",
    "        # 求每个位置左边最小的元素\n",
    "        for i in range(1,n):\n",
    "            leftMin[i]=min(leftMin[i-1],nums[i-1])\n",
    "        # 求右边比自己小的元素的最大值\n",
    "        stack=[]\n",
    "        for j in range(n-1,-1,-1):\n",
    "            numsk=float(\"-inf\")\n",
    "            while stack and stack[-1]<nums[j]:\n",
    "                numsk=stack.pop()\n",
    "            if leftMin[j]<numsk:\n",
    "                return True\n",
    "            stack.append(nums[j])\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "站内元素单调递减-j\n",
    "弹出元素是小于栈内某元素的-k\n",
    "从右往左遍历-i\n",
    "\n",
    "'''\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def find132pattern(self, nums: List[int]) -> bool:\n",
    "        stack = []\n",
    "        n = len(nums)\n",
    "        k = -inf\n",
    "        for a in nums[::-1]:\n",
    "            if a<k:return True\n",
    "            while stack and stack[-1]<a:\n",
    "                k = max(stack.pop(),k)\n",
    "            stack.append(a)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find132pattern(self, nums: List[int]) -> bool:\n",
    "        sousuojihe = []\n",
    "        l = len(nums)\n",
    "        low = nums[0]\n",
    "        high = nums[0]\n",
    "        xulie = 0\n",
    "        highest = high\n",
    "        sousuojihe.append([low, high])\n",
    "        for i in range(1, l):\n",
    "            if highest < nums[i]:\n",
    "                sousuojihe[xulie] = [low, nums[i]]\n",
    "                high = nums[i]\n",
    "                highest = nums[i]\n",
    "            elif nums[i] < low:\n",
    "                xulie = xulie + 1\n",
    "                low = nums[i]\n",
    "                high = nums[i]\n",
    "                sousuojihe.append([low, high])\n",
    "            else:\n",
    "                # print(sousuojihe[0][1])\n",
    "                # print(nums[i])\n",
    "                h = len(sousuojihe)\n",
    "                # print(sousuojihe)\n",
    "                for j in range(0, h):\n",
    "                    if nums[i] > sousuojihe[j][0] and nums[i] < sousuojihe[j][1]:\n",
    "                        return True\n",
    "                if nums[i] > high:\n",
    "                    high = nums[i]\n",
    "                    sousuojihe[xulie] = [low, high]\n",
    "        return False\n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find132pattern(self, nums: List[int]) -> bool:\n",
    "        # i < j < k\n",
    "        # n[i] < n[k] < n[j]       -1    3    2  # 下一个最小值\n",
    "        \n",
    "        min_value = float(\"inf\")\n",
    "        stack = []\n",
    "        \n",
    "        # 尽可能大。 【 6 4 3\n",
    "        res = [-1] * len(nums)\n",
    "        for i in range(len(nums)-1, -1, -1):\n",
    "            temp = -1\n",
    "            while stack and nums[stack[-1]] < nums[i]:\n",
    "                temp = stack.pop()\n",
    "            res[i] = temp\n",
    "            stack.append(i)\n",
    "        \n",
    "        for i in range(len(nums)):\n",
    "            if i == 0:\n",
    "                min_value = nums[0]\n",
    "                continue\n",
    "            if min_value < nums[i] and (res[i] != -1 and nums[res[i]] > min_value):\n",
    "                return True\n",
    "            min_value = min(min_value, nums[i])\n",
    "        return False\n",
    "                \n",
    "            \n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find132pattern(self, nums: List[int]) -> bool:\n",
    "        stack = []\n",
    "        nums = nums[::-1]\n",
    "        k = float('-inf')\n",
    "        for i in nums:\n",
    "            if (i < k):\n",
    "                return True\n",
    "            while stack and stack[-1]<i:\n",
    "                k = stack.pop()\n",
    "            stack.append(i)\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find132pattern(self, nums: List[int]) -> bool:\n",
    "        preMin = [float(\"inf\")] * len(nums)\n",
    "        n = len(nums)\n",
    "        for i in range(1, n):\n",
    "            preMin[i] = min(preMin[i-1], nums[i-1])\n",
    "        \n",
    "        stack = []\n",
    "        popedNum = None\n",
    "        for j in range(n-1, 0, -1):\n",
    "            while stack and stack[-1] < nums[j]:\n",
    "                popedNum = stack.pop()\n",
    "            if popedNum and popedNum > preMin[j]:\n",
    "                return True\n",
    "            stack.append(nums[j])\n",
    "\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find132pattern(self, nums: List[int]) -> bool:\n",
    "        n=len(nums)\n",
    "        leftMin=[float(\"inf\")]*n\n",
    "        # 求每个位置左边最小的元素\n",
    "        for i in range(1,n):\n",
    "            leftMin[i]=min(leftMin[i-1],nums[i-1])\n",
    "        # 求右边比自己小的元素的最大值\n",
    "        stack=[]\n",
    "        for j in range(n-1,-1,-1):\n",
    "            numsk=float(\"-inf\")\n",
    "            while stack and stack[-1]<nums[j]:\n",
    "                numsk=stack.pop()\n",
    "            if leftMin[j]<numsk:\n",
    "                return True\n",
    "            stack.append(nums[j])\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find132pattern(self, nums: List[int]) -> bool:\n",
    "        n=len(nums)\n",
    "        left_min=[inf]*n\n",
    "        for i in range(1,n):\n",
    "            left_min[i]=min(left_min[i-1],nums[i-1])\n",
    "        stack=[]\n",
    "        for j in range(n-1,-1,-1):\n",
    "            mask=-inf\n",
    "            while stack and stack[-1]<nums[j]:\n",
    "                mask=stack.pop()\n",
    "            if left_min[j]<mask:\n",
    "                return True\n",
    "            stack.append(nums[j])\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find132pattern(self, nums: List[int]) -> bool:\n",
    "        '''下面代码中的n即nums[i]，为最小值；栈顶stack[-1]保存的是最大值，即nums[j]; 栈弹出的更新nums_k，就是次大值，即nums[k]'''\n",
    "\n",
    "        stack = [] # 单调栈，用于保存目前最大的值，如果有比他更大的值，就弹出（次大值），然后添加更新最大值\n",
    "        num_k = float('-inf') # 中间数 k 值为次大（第二大），先定义为负无穷大\n",
    "        for n in nums[::-1]: # 从后往前遍历，如果有\n",
    "            if n < num_k: # 小于次小值，即n最小，满足条件，直接返回\n",
    "                return True\n",
    "            while stack and stack[-1] < n: # 找到新的更大值，需要更新最大值和次大值.此处用while是要保持栈顶最大。\n",
    "                num_k = stack.pop() # 次大值更新；因为有更大的值了，所以弹出原先旧的最大值（现在已经是次大值）\n",
    "            stack.append(n)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find132pattern(self, nums: List[int]) -> bool:\n",
    "        # i < j < k\n",
    "        # n[i] < n[k] < n[j]       -1    3    2  # 下一个最小值\n",
    "        \n",
    "        min_value = float(\"inf\")\n",
    "        stack = []\n",
    "        \n",
    "        # 尽可能大。 【 6 4 3\n",
    "        res = [-1] * len(nums)\n",
    "        for i in range(len(nums)-1, -1, -1):\n",
    "            temp = -1\n",
    "            while stack and nums[stack[-1]] < nums[i]:\n",
    "                temp = stack.pop()\n",
    "            res[i] = temp\n",
    "            stack.append(i)\n",
    "        \n",
    "        for i in range(len(nums)):\n",
    "            if i == 0:\n",
    "                min_value = nums[0]\n",
    "                continue\n",
    "            if min_value < nums[i] and (res[i] != -1 and nums[res[i]] > min_value):\n",
    "                return True\n",
    "            min_value = min(min_value, nums[i])\n",
    "        return False\n",
    "                \n",
    "            \n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find132pattern(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        mx_k = [-inf] * n\n",
    "        st = []\n",
    "        mx = -inf\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            x = nums[i]\n",
    "            while st and x > st[-1]:\n",
    "                mx = max(mx, st.pop())\n",
    "            st.append(x)\n",
    "            mx_k[i] = mx\n",
    "        # print(mx_k)\n",
    "        for i in range(n - 1):\n",
    "            if nums[i] < mx_k[i + 1]:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find132pattern(self, nums: List[int]) -> bool:\n",
    "        #单调栈的思考方式：寻找单调性\n",
    "        #本题单调性在于先递增后递减\n",
    "        #左侧最小化的最小值右侧最大化的最小值\n",
    "        if len(nums)<3:\n",
    "            return False\n",
    "        stk=[]\n",
    "        left=[inf]*(len(nums))\n",
    "        left[1]=nums[0]\n",
    "        for i in range(2,len(nums)):\n",
    "            left[i]=min(left[i-1],nums[i-1])\n",
    "        for i,num in enumerate(nums):\n",
    "            while stk and nums[stk[-1]]<=num:\n",
    "                stk.pop()\n",
    "            if len(stk)>=1 and nums[i]>left[stk[-1]]:\n",
    "                return True\n",
    "            stk.append(i)\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def find132pattern(self, nums):\n",
    "        N = len(nums)\n",
    "        leftMin = [float(\"inf\")] * N\n",
    "        for i in range(1, N):\n",
    "            leftMin[i] = min(leftMin[i - 1], nums[i - 1])\n",
    "        stack = []\n",
    "        for j in range(N - 1, -1, -1):\n",
    "            numsk = float(\"-inf\")\n",
    "            while stack and stack[-1] < nums[j]:\n",
    "                numsk = stack.pop()\n",
    "            if leftMin[j] < numsk:\n",
    "                return True\n",
    "            stack.append(nums[j])\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find132pattern(self, nums: List[int]) -> bool:\n",
    "        stack = []\n",
    "        num = float('-inf')\n",
    "        for n in nums[::-1]:\n",
    "            if n < num:\n",
    "                return True\n",
    "            while stack and stack[-1] < n:\n",
    "                num = stack.pop()\n",
    "            stack.append(n)\n",
    "        return False\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find132pattern(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        stack = [0]\n",
    "        min_val = [nums[0]]\n",
    "        for k in range(1, n):\n",
    "            while stack and nums[stack[-1]] <= nums[k]:\n",
    "                stack.pop()\n",
    "            if stack and min_val[stack[-1]] < nums[k]:\n",
    "                return True\n",
    "            stack.append(k)\n",
    "            min_val.append(min(min_val[-1], nums[k]))\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find132pattern(self, nums: List[int]) -> bool:\n",
    "        res = -float(\"inf\")\n",
    "        stack = []\n",
    "        for x in nums[::-1]:\n",
    "            if x < res:\n",
    "                return True\n",
    "            while stack and x > stack[-1]:\n",
    "                res= stack.pop()\n",
    "            stack.append(x)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find132pattern(self, nums: List[int]) -> bool:\n",
    "        stack = []\n",
    "        out = float('-inf') # 次大\n",
    "        for num in nums[::-1]:\n",
    "            if out > num:\n",
    "                return True\n",
    "            while stack and stack[-1] < num:\n",
    "                out = stack.pop()\n",
    "            stack.append(num)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find132pattern(self, nums: List[int]) -> bool:\n",
    "        st = []\n",
    "        max_pop = -inf\n",
    "        for x in nums[::-1]:\n",
    "            if max_pop > x: return True\n",
    "            while st and st[-1] < x: max_pop = max(max_pop,st.pop())\n",
    "            st.append(x)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find132pattern(self, nums: List[int]) -> bool:\n",
    "        # 暴力-----超时\n",
    "        # N = len(nums)\n",
    "        # numsi = nums[0]\n",
    "        # for j in range(1, N):\n",
    "        #     for k in range(N - 1, j, -1):\n",
    "        #         if numsi < nums[k] < nums[j]:\n",
    "        #             return True\n",
    "        #     numsi = min(numsi, nums[j])\n",
    "        # return False\n",
    "\n",
    "\n",
    "        # 单调栈\n",
    "        min_list = [nums[0]]\n",
    "        for i in range(1, len(nums)):\n",
    "            min_list.append(min(min_list[-1], nums[i]))\n",
    "        # min最小前缀数组\n",
    "\n",
    "        stack = []\n",
    "        for j in range(len(nums) - 1, -1, -1):\n",
    "            while stack and stack[-1] < nums[j]:\n",
    "                k = stack.pop()  # 在stack中找出k\n",
    "                if k > min_list[j]:\n",
    "                    return True\n",
    "            stack.append(nums[j])\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find132pattern(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        L_min = [0]*n\n",
    "        L_min[0] = nums[0]\n",
    "        for i in range(1,n):\n",
    "            L_min[i] = min([L_min[i-1],nums[i-1]])\n",
    "            \n",
    "        stack = []\n",
    "        for i in range(n-1,0,-1):\n",
    "            num_L = L_min[i]\n",
    "            num_M = nums[i]\n",
    "            num_R = None\n",
    "            while stack and stack[-1]<num_M:\n",
    "                num_R = stack.pop()\n",
    "                \n",
    "            if num_R is not None and num_R>num_L:\n",
    "                return(True)\n",
    "        \n",
    "            stack.append(num_M)\n",
    "        \n",
    "        return(False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find132pattern(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        max_k = []\n",
    "        second_k = float(\"-inf\")\n",
    "        for i in nums[::-1]:\n",
    "            if i < second_k:\n",
    "                return True\n",
    "            while max_k and i > max_k[-1]:\n",
    "                second_k = max_k.pop()\n",
    "            if i > second_k:\n",
    "                max_k.append(i)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find132pattern(self, nums: List[int]) -> bool:\n",
    "        arr1 = [nums[0]] * len(nums)\n",
    "        for i in range(1, len(nums)):\n",
    "            arr1[i] = min(arr1[i-1], nums[i])\n",
    "        s = []\n",
    "        for i in range(len(nums)-1, -1, -1):\n",
    "            val = nums[i]\n",
    "            while s and nums[i] > s[-1]:\n",
    "                val = s.pop()\n",
    "            s.append(nums[i])\n",
    "            if arr1[i] < val < nums[i]:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find132pattern(self, nums: List[int]) -> bool:\n",
    "        stack = deque()\n",
    "        k = -(10 ** 9 + 7)\n",
    "        for i in range(len(nums) - 1,-1,-1):\n",
    "            if nums[i] < k:\n",
    "                return True\n",
    "            while stack and stack[-1] < nums[i]:\n",
    "                k = max(k,stack.pop())\n",
    "            stack.append(nums[i])\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find132pattern(self, nums: List[int]) -> bool:\n",
    "        # 单调栈\n",
    "        stack = []\n",
    "        num = float('-inf')\n",
    "        for n in nums[::-1]:\n",
    "            if n<num:\n",
    "                return True\n",
    "            while stack and stack[-1]<n:\n",
    "                num = stack.pop()\n",
    "            stack.append(n)\n",
    "\n",
    "        return False\n",
    "\n",
    "            \n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find132pattern(self, nums: List[int]) -> bool:\n",
    "        stack=[]\n",
    "        max_2=-10**9\n",
    "        for i in nums[::-1]:\n",
    "            if i<max_2:\n",
    "                return True\n",
    "            while stack and stack[-1]<i:\n",
    "                max_2=stack.pop()\n",
    "            stack.append(i)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find132pattern(self, nums: List[int]) -> bool:\n",
    "        # 对于每一个nums[j]，求其左边最小的数字nums[i] (i<j)，同时找其右边比自己小的最大数字nums[k] (k>j)\n",
    "        l_mins = [float('inf')]  # l_mins[i] = [0,i]中最小的数字\n",
    "        for j in range(1, len(nums)):\n",
    "            l_mins.append(min(l_mins[-1], nums[j - 1]))\n",
    "        sorted_arr = []\n",
    "        for j in range(len(nums) - 1, -1, -1):\n",
    "            idx = bisect.bisect_left(sorted_arr, nums[j])\n",
    "            if idx - 1 >= 0 and l_mins[j] < sorted_arr[idx - 1] < nums[j]:\n",
    "                return True\n",
    "            sorted_arr.insert(idx, nums[j])\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find132pattern(self, nums: List[int]) -> bool:\n",
    "        stack=[[nums[0],nums[0]]]\n",
    "        min_num=nums[0]\n",
    "        for i,item in enumerate(nums):\n",
    "            if i==0:\n",
    "                continue\n",
    "            if item<min_num:\n",
    "                min_num=item\n",
    "                stack.append([item,item])\n",
    "                continue\n",
    "            elif item>min_num:\n",
    "                if item>stack[-1][1]:\n",
    "                    stack[-1][1]=item\n",
    "                if len(stack)>=2:\n",
    "                    new_item=[]\n",
    "                    for i in range(0,len(stack)-1):\n",
    "                        if stack[i][1]>item:\n",
    "                            new_item.append(stack[i])\n",
    "                    new_item.append(stack[-1])\n",
    "                    stack=new_item\n",
    "\n",
    "                for x in stack:\n",
    "                    if x[0]<item<x[1]:\n",
    "                        return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find132pattern(self, nums: List[int]) -> bool:\n",
    "        n=len(nums)\n",
    "        ll=[inf]*n\n",
    "        \n",
    "        for  i in range(n):\n",
    "            if i>0:\n",
    "              ll[i]=min(ll[i-1],nums[i-1])\n",
    "        sk=[]\n",
    "        for i in range(n-1,-1,-1):\n",
    "           nk=-inf \n",
    "           while sk and nums[sk[-1]]<nums[i]:\n",
    "            nk=nums[sk[-1]]\n",
    "            sk.pop()\n",
    "            \n",
    "           if nk>ll[i]:\n",
    "             return True\n",
    "           sk.append(i)        \n",
    "        return False       \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def find132pattern(self, nums):\n",
    "        N = len(nums)\n",
    "        leftMin = [float(\"inf\")] * N\n",
    "        for i in range(1, N):\n",
    "            leftMin[i] = min(leftMin[i - 1], nums[i - 1])\n",
    "        stack = []\n",
    "        for j in range(N - 1, -1, -1):\n",
    "            numsk = float(\"-inf\")\n",
    "            while stack and stack[-1] < nums[j]:\n",
    "                numsk = stack.pop()\n",
    "            if leftMin[j] < numsk:\n",
    "                return True\n",
    "            stack.append(nums[j])\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find132pattern(self, nums: List[int]) -> bool:\n",
    "        l = len(nums)\n",
    "        mins = [0] * l \n",
    "        mins[0] = nums[0]\n",
    "        for i in range(1, l):\n",
    "            mins[i] = min(mins[i-1], nums[i])\n",
    "        stack = [nums[-1]]\n",
    "        for j in range(l-2, -1, -1):\n",
    "            if nums[j] > mins[j]:\n",
    "                while stack and stack[-1] <= mins[j]:\n",
    "                    stack.pop()\n",
    "                if stack and stack[-1] < nums[j]:\n",
    "                    return True \n",
    "                stack.append(nums[j])\n",
    "        return False\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find132pattern(self, nums: List[int]) -> bool:\n",
    "\n",
    "        # 从右往左，保证n[k]<n[j]，在保证n[i]<n[k]，栈顶为j,最大值，历史出过栈的为k\n",
    "  \n",
    "        k = float(-inf)\n",
    "        stack = []\n",
    "        for n in nums[::-1]:\n",
    "            if n<k:\n",
    "                return True\n",
    "            while stack and n>stack[-1]:\n",
    "                k = max(k, stack.pop(-1))\n",
    "            stack.append(n)\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find132pattern(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        st = [[nums[0], nums[0]]]\n",
    "        for x in nums[1:]:\n",
    "            if x < st[-1][0]:\n",
    "                if st[-1][0] == st[-1][1]:\n",
    "                    st.pop()\n",
    "                st.append([x, x])\n",
    "            \n",
    "            left = st[-1][0]\n",
    "            right = x\n",
    "            while st and x > st[-1][0]:\n",
    "                if st[-1][1] > x:\n",
    "                    return True\n",
    "                right = max(x, st[-1][1])\n",
    "                st.pop()\n",
    "            st.append([left, right])\n",
    "        \n",
    "        return False\n",
    "\n",
    "        # pre_min = [inf] * n\n",
    "        # for i in range(1, n):\n",
    "        #     pre_min[i] = nums[i-1] if nums[i-1] < pre_min[i-1] else pre_min[i-1]\n",
    "        \n",
    "        # suf_min = inf\n",
    "        # suf_max = -inf\n",
    "        # for j in range(n-2, 0, -1):\n",
    "        #     suf_min = min(suf_min, nums[j+1])\n",
    "        #     suf_max = max(suf_max, nums[j+1])\n",
    "        #     if pre_min[j] < nums[j] and nums[j] > suf_min:\n",
    "        #         return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find132pattern(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        st = [[nums[0], nums[0]]]\n",
    "        for x in nums[1:]:\n",
    "            if x < st[-1][0]:\n",
    "                if st[-1][0] == st[-1][1]:\n",
    "                    st.pop()\n",
    "                st.append([x, x])\n",
    "            \n",
    "            left = st[-1][0]\n",
    "            right = x\n",
    "            while st and x > st[-1][0]:\n",
    "                if st[-1][1] > x:\n",
    "                    return True\n",
    "                right = max(x, st[-1][1])\n",
    "                st.pop()\n",
    "            st.append([left, right])\n",
    "        \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find132pattern(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        candidate_k = [nums[n - 1]]\n",
    "        max_k = float(\"-inf\")\n",
    "\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            if nums[i] < max_k:\n",
    "                return True\n",
    "            while candidate_k and nums[i] > candidate_k[-1]:\n",
    "                max_k = candidate_k[-1]\n",
    "                candidate_k.pop()\n",
    "            if nums[i] > max_k:\n",
    "                candidate_k.append(nums[i])\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find132pattern(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        record = [-1 for i in range(n)]\n",
    "        minA = []\n",
    "        for i in range(n):\n",
    "            num = nums[i]\n",
    "            if i == 0:\n",
    "                minA.append(num)\n",
    "            else:\n",
    "                minA.append(min(num, minA[-1]))\n",
    "        print(\"nums:\", nums)\n",
    "        print(\"minA:\", minA)\n",
    "        stack = []\n",
    "        for i in range(n):\n",
    "            if i == 0:\n",
    "                stack.append(i)\n",
    "            else:\n",
    "                if nums[i] < nums[stack[-1]]:\n",
    "                    record[i] = stack[-1]\n",
    "                    stack.append(i)\n",
    "                else:\n",
    "                    while stack != [] and nums[i] >= nums[stack[-1]]:\n",
    "                        stack.pop()\n",
    "                    if stack == []:\n",
    "                        stack.append(i)\n",
    "                    else:\n",
    "                        record[i] = stack[-1]\n",
    "                        stack.append(i)\n",
    "        print(\"record:\", record)\n",
    "        for i in range(n-1, 1, -1):\n",
    "            if record[i] == -1 or record[i] == 0:\n",
    "                continue\n",
    "            t2 = nums[i]\n",
    "            t3 = nums[record[i]]\n",
    "            t1 = minA[record[i] - 1]\n",
    "            if t3 > t2 and t2 > t1:\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "132 模式的子序列 由三个整数 nums[i]、nums[j] 和 nums[k] 组成，并同时满足：i < j < k 和 nums[i] < nums[k] < nums[j] 。\n",
    "\n",
    "可以通过 枚举 i, j, k 来寻找答案, 不过 枚举 i 更为简单.\n",
    "\n",
    "倒序枚举 nums[i], 用(递减)单调栈 st 记录元素, 如果 nums[i] 比 st[-1] 大, 那么弹出 st[-1].\n",
    "此时 就找到了 nums[j](对应 nums[i]), nums[k](对应弹出的 st[-1]).\n",
    "为了更容易找到 nums[i], 应该保证 nums[k] 尽可能大, \n",
    "因此需要 k 记录栈 st 弹出最大的元素(可以保证从栈中弹出的元素都是符合题意得 nums[k])\n",
    "\n",
    "当 nums[i] < k 时, 说明找到了 132 模式得子序列\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def find132pattern(self, nums: List[int]) -> bool:\n",
    "        st = []\n",
    "        n = len(nums)\n",
    "        \n",
    "        k = -inf\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if nums[i] < k:\n",
    "                return True\n",
    "            while st and nums[i] > st[-1]:\n",
    "                k = max(k, st.pop())\n",
    "            st.append(nums[i])\n",
    "        \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find132pattern(self, nums: List[int]) -> bool:\n",
    "        ak = float(\"-inf\")\n",
    "        stack = []\n",
    "        for num in reversed(nums):\n",
    "            if ak > num: \n",
    "                return True\n",
    "            while stack and stack[-1] < num:\n",
    "                ak = stack.pop()\n",
    "            stack.append(num)\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find132pattern(self, nums: List[int]) -> bool:\n",
    "        n,minNum = len(nums),-inf\n",
    "        stack = []\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if nums[i] < minNum:\n",
    "                return True\n",
    "            while stack and stack[-1] < nums[i]:\n",
    "                minNum = stack.pop()\n",
    "            stack.append(nums[i])\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find132pattern(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        if n < 3:\n",
    "            return False\n",
    "        \n",
    "        stack = []  # Stack to keep track of potential \"2\" elements (nums[j])\n",
    "        third = float('-inf')  # Initialize the third element as negative infinity\n",
    "        \n",
    "        for i in range(n-1, -1, -1):\n",
    "            if nums[i] < third:\n",
    "                return True\n",
    "            while stack and nums[i] > stack[-1]:\n",
    "                third = stack.pop()\n",
    "            stack.append(nums[i])\n",
    "        \n",
    "        return False\n",
    "\n",
    "    # def find132pattern(self, nums: List[int]) -> bool:\n",
    "    #     n = len(nums)\n",
    "    #     sorted_nums = list(enumerate(nums))\n",
    "    #     sorted_nums = sorted(sorted_nums, key=lambda x: x[1])\n",
    "    #     for i in range(n):\n",
    "    #         small_idx = sorted_nums[i][0]\n",
    "    #         for j in range(n - 1, i, -1):\n",
    "    #             large_idx = sorted_nums[j][0]\n",
    "    #             if small_idx < large_idx and large_idx < n - 1:\n",
    "    #                 for idx, ele in sorted_nums[i + 1: j]:\n",
    "    #                     if idx > large_idx and nums[idx] != nums[large_idx] and nums[idx] != nums[small_idx]:\n",
    "    #                         return True\n",
    "        \n",
    "    #     return False\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find132pattern(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        premin = [float('inf')] * n\n",
    "        stack = []\n",
    "        for i in range(n):\n",
    "            premin[i] = min(premin[i - 1], nums[i])\n",
    "            while stack and nums[stack[-1]] <= nums[i]:\n",
    "                stack.pop()\n",
    "            if stack and premin[stack[-1]] < nums[i]:\n",
    "                return True\n",
    "            stack.append(i)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find132pattern(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        candidate_k = [nums[n - 1]]\n",
    "        max_k = float(\"-inf\")\n",
    "\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            if nums[i] < max_k:\n",
    "                return True\n",
    "            while candidate_k and nums[i] > candidate_k[-1]:\n",
    "                max_k = candidate_k[-1]\n",
    "                candidate_k.pop()\n",
    "            if nums[i] > max_k:\n",
    "                candidate_k.append(nums[i])\n",
    "\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find132pattern(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        st = [nums[-1]]\n",
    "        removed_max = -inf\n",
    "        for i in range(n-2, -1, -1):\n",
    "            num = nums[i]\n",
    "            if num < removed_max:\n",
    "                return True\n",
    "            \n",
    "            while st and num > st[-1]:\n",
    "                removed_max = st.pop()\n",
    "            \n",
    "            if num > removed_max:\n",
    "                st.append(num)\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find132pattern(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        st = []\n",
    "        pre_min = [inf]\n",
    "        for i, x in enumerate(nums):\n",
    "            while st and nums[st[-1]] <= x:\n",
    "                st.pop()\n",
    "            if st and pre_min[st[-1]] < x:\n",
    "                return True\n",
    "            st.append(i)\n",
    "            pre_min.append(min(pre_min[-1], x))\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import *\n",
    "import bisect\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def find132pattern(self, nums: List[int]) -> bool:\n",
    "        if len(nums) < 3:\n",
    "            return False\n",
    "        left_min = nums[0]\n",
    "        right_all = SortedList(nums[2:])\n",
    "        for i in range(1, len(nums)-1):\n",
    "            if left_min < nums[i]:\n",
    "                j = bisect.bisect_right(right_all, left_min)\n",
    "                if j < len(right_all) and right_all[j] < nums[i]:\n",
    "                    return True\n",
    "            left_min = min(left_min, nums[i])\n",
    "            right_all.remove(nums[i + 1])\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find132pattern(self, nums: List[int]) -> bool:\n",
    "        stack = []\n",
    "        k = -(10 ** 9 + 7)\n",
    "        for i in range(len(nums) - 1,-1,-1):\n",
    "            if nums[i] < k:\n",
    "                return True\n",
    "            while stack and stack[-1] < nums[i]:\n",
    "                k = max(k,stack.pop())\n",
    "            stack.append(nums[i])\n",
    "        return False\n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers.sortedlist import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def find132pattern(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        if n < 3:\n",
    "            return False\n",
    "        r_sortedlist = SortedList(nums[2:])\n",
    "        l_min = nums[0]\n",
    "        for i in range(1,n - 1):\n",
    "            idx = r_sortedlist.bisect_right(l_min)\n",
    "            if idx < len(r_sortedlist) and r_sortedlist[idx] < nums[i]:\n",
    "                return True\n",
    "            l_min = min(l_min,nums[i])\n",
    "            r_sortedlist.remove(nums[i + 1])\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def find132pattern(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        if n < 3:\n",
    "            return False\n",
    "        \n",
    "        # 左侧最小值\n",
    "        left_min = nums[0]\n",
    "        # 右侧所有元素\n",
    "        right_all = SortedList(nums[2:])\n",
    "        \n",
    "        for j in range(1, n - 1):\n",
    "            if left_min < nums[j]:\n",
    "                index = right_all.bisect_right(left_min)\n",
    "                if index < len(right_all) and right_all[index] < nums[j]:\n",
    "                    return True\n",
    "            left_min = min(left_min, nums[j])\n",
    "            right_all.remove(nums[j + 1])\n",
    "\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find132pattern(self, nums: List[int]) -> bool:\n",
    "        des_stack = []\n",
    "        k_num =  -inf\n",
    "        \n",
    "        for i in range(len(nums)-1, -1, -1):\n",
    "            i_num = nums[i]\n",
    "            if i_num < k_num:\n",
    "                return True\n",
    "            # 'while' -> 排空stack \n",
    "            while des_stack and des_stack[-1] < i_num:\n",
    "                k_num = max(k_num, des_stack.pop())\n",
    "            des_stack.append(i_num)\n",
    "\n",
    "        return False \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find132pattern(self, nums: List[int]) -> bool:\n",
    "        N = len(nums)\n",
    "        stack = [nums[-1]]\n",
    "        n3 = -10**9-1\n",
    "        for i in range(N-2,-1,-1):\n",
    "            n = nums[i]\n",
    "            if n>=stack[-1]:\n",
    "                while len(stack)>0 and n>stack[-1]:\n",
    "                    n2=stack.pop()\n",
    "                    n3 = max(n2,n3)\n",
    "                stack.append(n)\n",
    "            else:\n",
    "                if n<n3:\n",
    "                    return True \n",
    "                stack.append(n)\n",
    "\n",
    "\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find132pattern(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        candidate_k = [nums[n - 1]]\n",
    "        max_k = float(\"-inf\")\n",
    "\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            if nums[i] < max_k:\n",
    "                return True\n",
    "            while candidate_k and nums[i] > candidate_k[-1]:\n",
    "                max_k = candidate_k[-1]\n",
    "                candidate_k.pop()\n",
    "            if nums[i] > max_k:\n",
    "                candidate_k.append(nums[i])\n",
    "\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    #from sortedcontainers import SortedList\n",
    "    #from sortedcontainers import SortedList\n",
    "    def find132pattern(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        if n <3:\n",
    "            return False\n",
    "        left_min = nums[0]\n",
    "        #right_all = SortedList(nums[2:])\n",
    "        from sortedcontainers import SortedList\n",
    "        right_all = SortedList(nums[2:])\n",
    "        for j in range(1, n-1):\n",
    "            if left_min < nums[j]:\n",
    "                index = right_all.bisect_right(left_min)\n",
    "                if index < len(right_all) and right_all[index] < nums[j]:\n",
    "                    return True\n",
    "                \n",
    "            left_min = min(left_min, nums[j])\n",
    "            right_all.remove(nums[j+1])\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find132pattern(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        candidate_k = [nums[n - 1]]\n",
    "        max_k = float(\"-inf\")\n",
    "\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            if nums[i] < max_k:\n",
    "                return True\n",
    "            while candidate_k and nums[i] > candidate_k[-1]:\n",
    "                max_k = candidate_k[-1]\n",
    "                candidate_k.pop()\n",
    "            if nums[i] > max_k:\n",
    "                candidate_k.append(nums[i])\n",
    "\n",
    "        return False\n",
    "        '''\n",
    "        if max(nums) - min(nums) < 2:\n",
    "            return False\n",
    "        for i in range(0,len(nums)):\n",
    "            for j in range(i+1,len(nums)):\n",
    "                if nums[j] > nums[i]:\n",
    "                    for k in range(j+1,len(nums)):\n",
    "                        if nums[k] > nums[i] and nums[k] < nums[j]:\n",
    "                            return True\n",
    "        \n",
    "        return False\n",
    "        '''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import *\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def find132pattern(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        if n < 3:\n",
    "            return False\n",
    "        left_min = nums[0]\n",
    "        right_all = SortedList(nums[2:])\n",
    "        for i in range(1, n - 1):\n",
    "            if left_min < nums[i]:\n",
    "                j = bisect.bisect_right(right_all,left_min)\n",
    "                if j < len(right_all) and right_all[j] < nums[i]:\n",
    "                    return True\n",
    "            left_min = min(left_min, nums[i])\n",
    "            right_all.remove(nums[i+1])\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find132pattern(self, nums: List[int]) -> bool:\n",
    "        stack = []\n",
    "        thrid = float('-inf')\n",
    "        n = len(nums)\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if nums[i] < thrid:\n",
    "                return True\n",
    "\n",
    "            while stack and nums[i] > stack[-1]:\n",
    "                thrid = stack[-1]\n",
    "                stack.pop()\n",
    "            stack.append(nums[i])\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find132pattern(self, nums: List[int]) -> bool:\n",
    "        stack = []\n",
    "        k = -(10 ** 9 + 7)\n",
    "        for i in range(len(nums) - 1,-1,-1):\n",
    "            if nums[i] < k:\n",
    "                return True\n",
    "            while stack and stack[-1] < nums[i]:\n",
    "                k = max(k,stack.pop())\n",
    "            stack.append(nums[i])\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find132pattern(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        min_array = [float('inf')] * n\n",
    "        min_array[0] = nums[0]\n",
    "        for i in range(n):\n",
    "            min_array[i] = min(nums[i], min_array[i - 1])\n",
    "        stack = []\n",
    "        for j in range(n - 1, -1, -1):\n",
    "            #<= 或 == 都可以，最极端只会==\n",
    "            if nums[j] <= min_array[j]:\n",
    "                continue\n",
    "            #这里不做普通单调栈的判断，而是判断\"j点前最小\"和\"j点后最小\"谁大\n",
    "            while stack and min_array[j] >= stack[-1]:\n",
    "                #如果\"j点前最小\"比\"j点后最小\"大，可以扔掉\"j点后最小\"\n",
    "                stack.pop()\n",
    "                #前面已经判断了j>i，这里直接判断j>j后，满足条件就返回True\n",
    "            if stack and stack[-1] < nums[j]:\n",
    "                return True\n",
    "            stack.append(nums[j])\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find132pattern(self, nums: List[int]) -> bool:\n",
    "        stack = []\n",
    "        min_val = inf\n",
    "        for n in nums:\n",
    "            while stack and n>stack[-1][0]:\n",
    "                stack.pop()\n",
    "            if stack and stack[-1][1]< n<stack[-1][0] :\n",
    "                return True\n",
    "            stack.append((n,min_val))\n",
    "            if n<min_val:\n",
    "                min_val = n\n",
    "        return False\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find132pattern(self, nums: List[int]) -> bool:\n",
    "        '''\n",
    "        单调栈法，找到满足条件的(k, j)对，维护单调递减\n",
    "        i则是通过遍历过程中与k比较得到的\n",
    "        具体来说，逆序遍历，找到满足ikj的最大k\n",
    "        '''\n",
    "        import sys\n",
    "        n = len(nums)\n",
    "        stack = []\n",
    "        k = -1 * sys.maxsize - 1\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if nums[i] < k:\n",
    "                return True\n",
    "            while stack and stack[-1] < nums[i]:\n",
    "                # 找满足(k,j)对的最大k\n",
    "                k = max(k, stack.pop())\n",
    "            stack.append(nums[i])\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find132pattern(self, nums: List[int]) -> bool:\n",
    "        stack = []\n",
    "        k = -(10 ** 9 + 7)\n",
    "        for idx in range(len(nums) - 1, -1, -1):\n",
    "            i = nums[idx]\n",
    "            if i < k:\n",
    "                return True\n",
    "            while stack and stack[-1] < i:\n",
    "                k = max(k, stack.pop())\n",
    "            stack.append(i)\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find132pattern(self, nums: List[int]) -> bool:\n",
    "        stack = []\n",
    "        k = -(10 ** 9 + 7)\n",
    "        for i in range(len(nums) - 1,-1,-1):\n",
    "            if nums[i] < k:\n",
    "                return True\n",
    "            while stack and stack[-1] < nums[i]:\n",
    "                k = max(k,stack.pop())\n",
    "            stack.append(nums[i])\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find132pattern(self, nums: List[int]) -> bool:\n",
    "        stack = [nums[-1]]\n",
    "        max_k = float(\"-inf\")\n",
    "\n",
    "        for i in range(len(nums) - 2,-1,-1):\n",
    "            if nums[i] < max_k:\n",
    "                return True\n",
    "            while stack and nums[i] > stack[-1]:\n",
    "                max_k = stack.pop()\n",
    "            if nums[i] > max_k:\n",
    "                stack.append(nums[i])\n",
    "        \n",
    "        return False\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find132pattern(self, nums: List[int]) -> bool:\n",
    "        arr = []\n",
    "        n = len(nums)\n",
    "        ma = -inf\n",
    "        for i in range(n - 1, - 1, - 1):\n",
    "            if nums[i] < ma:\n",
    "                return True\n",
    "            t = nums[i]\n",
    "            while arr and t > arr[-1]:\n",
    "                ma = max(ma, arr.pop())\n",
    "            arr.append(t)\n",
    "        return False     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import sortedcontainers\n",
    "class Solution:\n",
    "    def find132pattern(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        if n < 3:\n",
    "            return False\n",
    "        \n",
    "        # 左侧最小值\n",
    "        left_min = nums[0]\n",
    "        # 右侧所有元素\n",
    "        right_all = sortedcontainers.SortedList(nums[2:])\n",
    "        \n",
    "        for j in range(1, n - 1):\n",
    "            if left_min < nums[j]:\n",
    "                index = right_all.bisect_right(left_min)\n",
    "                if index < len(right_all) and right_all[index] < nums[j]:\n",
    "                    return True\n",
    "            left_min = min(left_min, nums[j])\n",
    "            right_all.remove(nums[j + 1])\n",
    "\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find132pattern(self, nums: List[int]) -> bool:\n",
    "        \n",
    "        N = len(nums)\n",
    "        monoStack = []\n",
    "        k = float('-inf')\n",
    "\n",
    "        for i in range(N-1, -1, -1):\n",
    "            if nums[i] < k:\n",
    "                return True\n",
    "            \n",
    "            while monoStack and nums[i] > monoStack[-1]:\n",
    "                tmp = monoStack.pop()\n",
    "                k = max(k, tmp)\n",
    "            \n",
    "            monoStack.append(nums[i])\n",
    "        \n",
    "        return False\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find132pattern(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        monotone = [nums[n - 1]]\n",
    "        maxK = float(\"-inf\")\n",
    "\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            if nums[i] < maxK:\n",
    "                return True\n",
    "            while monotone and nums[i] > monotone[-1]:\n",
    "                maxK = monotone.pop()\n",
    "            monotone.append(nums[i])\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find132pattern(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        if n <= 2:\n",
    "            return False\n",
    "        min_num = nums[0]\n",
    "        stack = []\n",
    "        for i in range(1,n):\n",
    "            while stack and nums[i] >= stack[-1][0]:\n",
    "                stack.pop()\n",
    "            if stack and nums[i] > stack[-1][-1]:\n",
    "                return True\n",
    "            stack.append((nums[i],min_num))\n",
    "            min_num = min(nums[i],min_num)\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def find132pattern(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        if n < 3:\n",
    "            return False\n",
    "        numI = nums[0]\n",
    "        storeK = SortedList(nums[2:])\n",
    "        for j in range(1,n-1):\n",
    "            if numI < nums[j]:\n",
    "                index = storeK.bisect_right(numI)\n",
    "                # print(numI)\n",
    "                # print(index)\n",
    "                # print(storeK)\n",
    "                if index < len(storeK) and storeK[index] < nums[j]:\n",
    "                    return True\n",
    "            numI = min(numI, nums[j])\n",
    "            storeK.remove(nums[j+1])\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def find132pattern(self, nums: List[int]) -> bool:\n",
    "#         n = len(nums)\n",
    "#         if n <= 2:\n",
    "#             return False\n",
    "#         min_num = max_num = nums[0]\n",
    "#         for i in range(1,len(nums)):\n",
    "#             if min_num < nums[i] < max_num:\n",
    "#                 return True\n",
    "#             min_num = min(nums[i],min_num)\n",
    "#             max_num = max(nums[i],max_num)\n",
    "#         return False\n",
    "\n",
    "class Solution:\n",
    "    def find132pattern(self, nums: List[int]) -> bool:\n",
    "        if len(nums) < 3:\n",
    "            return False\n",
    "\n",
    "        # 初始化栈和第三个元素的最大可能值\n",
    "        stack = []\n",
    "        third_element_max = float('-inf')\n",
    "\n",
    "        # 从数组末尾开始遍历\n",
    "        for i in range(len(nums) - 1, -1, -1):\n",
    "            # 检查是否找到132模式\n",
    "            if nums[i] < third_element_max:\n",
    "                return True\n",
    "            # 更新栈和第三个元素的最大可能值\n",
    "            while stack and stack[-1] < nums[i]:\n",
    "                third_element_max = stack.pop()\n",
    "            stack.append(nums[i])\n",
    "\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find132pattern(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        stack = [nums[n - 1]]\n",
    "        second = float('-inf')\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            if nums[i] < second:\n",
    "                return True\n",
    "            while stack and nums[i] > stack[-1]:\n",
    "                second = stack.pop()\n",
    "            stack.append(nums[i])\n",
    "        return False \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def find132pattern(self, nums: List[int]) -> bool:\n",
    "        #思路：遍历3\n",
    "        # if len(nums) < 3:\n",
    "        #     return False\n",
    "        # left_min = nums[0]\n",
    "        # right_sl = SortedList(nums[2:])\n",
    "        # for j in range(1, len(nums) - 1):\n",
    "        #     if nums[j] > left_min:\n",
    "        #         right_index = right_sl.bisect_right(left_min) #找到nums[j]的插入位置（右边界）\n",
    "        #         if right_index < len(right_sl) and right_sl[right_index] < nums[j]:\n",
    "        #             return True \n",
    "        #     left_min = min(nums[j], left_min)\n",
    "        #     right_sl.remove(nums[j+1]) #为下一轮做准备\n",
    "        \n",
    "        # return False\n",
    "\n",
    "        #思路：遍历1，从右往左扫描\n",
    "        n = len(nums)\n",
    "        if n < 3:\n",
    "            return False\n",
    "        stack = [nums[n-1]] #最后一个\n",
    "        max_k = float('-inf')\n",
    "\n",
    "        for i in range(n-2, -1, -1):\n",
    "            if nums[i] < max_k:\n",
    "                return True \n",
    "            while stack and stack[-1] < nums[i]:\n",
    "                max_k = stack[-1]\n",
    "                stack.pop()\n",
    "\n",
    "            stack.append(nums[i])\n",
    "        \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 枚举3\n",
    "    def find132pattern3(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        if n < 3:\n",
    "            return False\n",
    "        \n",
    "        # 左侧最小值\n",
    "        left_min = nums[0]\n",
    "        # 右侧所有元素\n",
    "        right_all = SortedList(nums[2:])\n",
    "        \n",
    "        for j in range(1, n - 1):\n",
    "            if left_min < nums[j]:\n",
    "                index = right_all.bisect_right(left_min)\n",
    "                if index < len(right_all) and right_all[index] < nums[j]:\n",
    "                    return True\n",
    "            left_min = min(left_min, nums[j])\n",
    "            right_all.remove(nums[j + 1])\n",
    "\n",
    "        return False\n",
    "\n",
    "\n",
    "    # 枚举2\n",
    "    def find132pattern2(self, nums: List[int]) -> bool:\n",
    "        candidate_i, candidate_j = [-nums[0]], [-nums[0]]\n",
    "\n",
    "        for v in nums[1:]:\n",
    "            idx_i = bisect.bisect_right(candidate_i, -v)\n",
    "            idx_j = bisect.bisect_left(candidate_j, -v)\n",
    "            if idx_i < idx_j:\n",
    "                return True\n",
    "\n",
    "            if v < -candidate_i[-1]:\n",
    "                candidate_i.append(-v)\n",
    "                candidate_j.append(-v)\n",
    "            elif v > -candidate_j[-1]:\n",
    "                last_i = -candidate_i[-1]\n",
    "                while candidate_j and v > -candidate_j[-1]:\n",
    "                    candidate_i.pop()\n",
    "                    candidate_j.pop()\n",
    "                candidate_i.append(-last_i)\n",
    "                candidate_j.append(-v)\n",
    "\n",
    "        return False\n",
    "\n",
    "    # 枚举1\n",
    "    def find132pattern(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        candidate_k = [nums[n - 1]]\n",
    "        max_k = float(\"-inf\")\n",
    "\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            if nums[i] < max_k:\n",
    "                return True\n",
    "            while candidate_k and nums[i] > candidate_k[-1]:\n",
    "                max_k = candidate_k[-1]\n",
    "                candidate_k.pop()\n",
    "            if nums[i] > max_k:\n",
    "                candidate_k.append(nums[i])\n",
    "\n",
    "        return False"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
